Introduction

This project report will address the implementation of three reinforcment learning algorithms on a custom grid world goal searching problem. The grid world problem is defined as follows:

Given an agent that starts in a specified state, this agent's goal is to reach the goal state. The goal state has reward 1, all other non-terminal states have reward 0. At each state, an agent has four actions: North, South, East, and West. For our problem, these actions will be deterministic. If an agent takes an action, the action will move the agent to the corresponding state. If an action will move an agent out of the grid, the agent will remain in the same position.

It is possible to create walls and/or other terminal states with different positive/negative rewards. However, our main focus here will be comparing the performance of the following three reinforcement learining algorthms:

  1. Q-learning
  2. Double Q-learning
  3. Monte Carlo

With each algorithm, we will use an $\epsilon$-greedy approach where we will take the action with the best value with 1-$\epsilon$ probability and take a random action with probability $\epsilon$. Taking the action with the best value out of the current information is known as exploitation, while taking a random action is known as exploration.

For all experiments, we will use a 5x5 grid world where the starting state is (0, 0) and the end state is (4, 4).

Q-Learning

Description and Psuedocode

In a standard Q-learning approach, for every possible state and action, there is a Q-value. This Q-value represents the utility of an action in a particular state; that is, roughly, the expected future reward R when taking action A in state S. An agent in this grid world will continuously take actions until it reaches a terminal state, updating its Q-values as it goes. The set of actions taken from the starting state to a terminal state represents an episode. Q-values are updated throughout an episode according to (1):

$$Q(s, a)<-Q(s, a) + R+\gamma*max_aQ(s', a') (1) $$

Note that here, $s$ is the current state, $a$ is the current action, $s'$ is the next state, and $a'$ represents an action from $s'$. $\gamma$ represents the discount factor for q-values. We will implement a standard Q-learning algorithm according to the psuedocode in Figure 1:

In [1]:
#imports

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
import random
import cv2
import seaborn as sns
In [2]:
img = cv2.imread('Q-learning psuedocode.jpg')
plt.figure(figsize=(8, 8))
plt.imshow(img)
plt.xlabel('Figure 1')
plt.show()

Implementation

The rest of our implementation steps are detailed below:

In [3]:
As=np.asarray(['North', 'South', 'East', 'West']) #possible actions

Rs=np.zeros((5, 5)) #initalize rewards for each state
Rs[4][4]=1 #goal state has reward of 1

S=list((0, 0)) #starting state

epsilon=0.1
gamma=0.9

runs=1000
episodes=50

steps_per_episode=np.empty((runs, episodes))

for i in range(runs):    
    q_table=np.zeros((5, 5, 4))
    for j in range(episodes):
        count=0
        while S !=[4, 4]:        
            p=random.random()
            if p<1-epsilon:
                A=np.argmax(q_table[S[0]][S[1]])
                if As[A]=='North':        
                    S_prime=list(S)
                    S_prime[1]+=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)                
                    q_table[S[0]][S[1]][A]=Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(q_table[S_prime[0]][S_prime[1]]))
                    S=S_prime                
                elif As[A]=='South':
                    S_prime=list(S)
                    S_prime[1]-=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    q_table[S[0]][S[1]][A]=Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(q_table[S_prime[0]][S_prime[1]]))
                    S=S_prime                
                elif As[A]=='East':
                    S_prime=list(S)
                    S_prime[0]+=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    q_table[S[0]][S[1]][A]=Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(q_table[S_prime[0]][S_prime[1]]))
                    S=S_prime                
                elif As[A]=='West':
                    S_prime=list(S)
                    S_prime[0]-=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    q_table[S[0]][S[1]][A]=Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(q_table[S_prime[0]][S_prime[1]]))
                    S=S_prime
                count+=1
            else:            
                A=np.random.randint(0, len(As))
                if As[A]=='North':        
                    S_prime=list(S)
                    S_prime[1]+=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    q_table[S[0]][S[1]][A]=Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(q_table[S_prime[0]][S_prime[1]]))
                    S=S_prime                
                elif As[A]=='South':
                    S_prime=list(S)
                    S_prime[1]-=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    q_table[S[0]][S[1]][A]=Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(q_table[S_prime[0]][S_prime[1]]))
                    S=S_prime                
                elif As[A]=='East':
                    S_prime=list(S)
                    S_prime[0]+=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    q_table[S[0]][S[1]][A]=Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(q_table[S_prime[0]][S_prime[1]]))
                    S=S_prime                
                elif As[A]=='West':
                    S_prime=list(S)
                    S_prime[0]-=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    q_table[S[0]][S[1]][A]=Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(q_table[S_prime[0]][S_prime[1]]))
                    S=S_prime
                count+=1
        S=list((0, 0))
        steps_per_episode[i][j]=count

Results

For this experiment, we ran the gridworld for 1000 iterations of 50 episodes each with an $\epsilon$ of 0.1 and a $\gamma$ of 0.9.

We first show the step-to-goal curve, visualizing the number of steps per episode it took for the agent to reach its goal. We obtain it by counting the number of steps it took for the agent to reach its goal in each episode, then averaging these counts over the 1000 iterations:

In [4]:
average_steps_per_episode=np.mean(steps_per_episode, axis=0)

plt.plot(average_steps_per_episode)
plt.xlabel('Episode')
plt.ylabel('Average number of Steps to reach goal')
plt.show()

Below we can see the V-table for one of the episodes:

In [5]:
v_table=np.zeros((5, 5))

for i in range(5):
    for j in range(5):
        v_table[i][j]=np.max(q_table[i][j])

grid=sns.heatmap(v_table, annot=True)
grid
Out[5]:
<matplotlib.axes._subplots.AxesSubplot at 0x202d1fc6148>

Conclusions

From the step-to-goal curve, we can see that with an epsilon of 0.1, by the 7th episode, the agent has learned the optimal policy and the step-to-goal-curve converges. In the first 7 epsisodes, we can see that the agent is exploring to try and find the optimal policy.

From the V-table, we can see that the optimal policy that the agent learned involves moving East 4 times, and North four times, leading to a rough average of 8 steps per episode.

Double Q-Learning

Description and Psuedocode

Double Q-learning follows a similar approach to Q-learning, except that there are now two q-values for each state s and action a. Thus, we must train two action-value functions $Q_1$ and $Q_2$. However, they are independent of each other, so they cannot be trained on the same time step or simultaneously. So, we will pick $Q_1$ or $Q_2$ at random to be updated on each time step. If we update $Q_1$, we will use $Q_2$ as the q-values of the next state, and vice-versa for $Q_2$. Action selection will be $\epsilon$-greedy with respect to the sum of $Q_1$ and $Q_2.$ The double Q-learning algorithm has the psuedocode in Figure 2:

In [6]:
img = cv2.imread('Double Q-learning psuedocode.jpg')
plt.figure(figsize=(16, 16))
plt.imshow(img)
plt.xlabel('Figure 2')
plt.show()

So we update $Q_1$ according to (2):

$$Q_1(S, A)<-Q_1(S, A)+\alpha(R+\gamma Q_2(S', argmax_a Q_1(S', a))-Q_1(S, A))$$ 
                                        (2)

And we update $Q_2$ according to (3):

$$Q_2(S, A)<-Q_2(S, A) +\alpha(R+\gamma Q_1(S', argmax_a Q_2(S', a))-Q_2(S, A))$$ 
                                       (3)

Note that $\alpha$ is the learning rate parameter for double q-larning.

Implementation

The rest of our implementation steps are detailed below:

In [7]:
As=np.asarray(['North', 'South', 'East', 'West']) #possible actions

Rs=np.zeros((5, 5)) #initalize rewards for each state
Rs[4][4]=1 #goal state has reward of 1

S=list((0, 0)) #starting state

epsilon=0.1
gamma=0.9
alpha=0.5

runs=1000
episodes=50

steps_per_episode_double=np.empty((runs, episodes))

for i in range(runs):
    q1_table=np.zeros((5, 5, 4))
    q2_table=np.zeros((5, 5, 4))
    qsum_table=np.zeros((5, 5, 4))
    for j in range(episodes):
        count=0
        while S !=[4, 4]:        
            p_e=random.random()
            if p_e<1-epsilon:
                A=np.argmax(qsum_table[S[0]][S[1]])
                if As[A]=='North':        
                    S_prime=list(S)
                    S_prime[1]+=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    p_q=random.random()
                    if p_q<0.5:
                        q1_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q2_table[S_prime[0]][S_prime[1]]))-q1_table[S[0]][S[1]][A])
                    else:
                        q2_table[S[0]][S[1]][A]=q2_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q1_table[S_prime[0]][S_prime[1]]))-q2_table[S[0]][S[1]][A])
                    qsum_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+q2_table[S[0]][S[1]][A]
                    S=S_prime                
                elif As[A]=='South':
                    S_prime=list(S)
                    S_prime[1]-=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    p_q=random.random()
                    if p_q<0.5:
                        q1_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q2_table[S_prime[0]][S_prime[1]]))-q1_table[S[0]][S[1]][A])
                    else:
                        q2_table[S[0]][S[1]][A]=q2_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q1_table[S_prime[0]][S_prime[1]]))-q2_table[S[0]][S[1]][A])
                    qsum_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+q2_table[S[0]][S[1]][A]
                    S=S_prime                
                elif As[A]=='East':
                    S_prime=list(S)
                    S_prime[0]+=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    p_q=random.random()
                    if p_q<0.5:
                        q1_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q2_table[S_prime[0]][S_prime[1]]))-q1_table[S[0]][S[1]][A])
                    else:
                        q2_table[S[0]][S[1]][A]=q2_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q1_table[S_prime[0]][S_prime[1]]))-q2_table[S[0]][S[1]][A])
                    qsum_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+q2_table[S[0]][S[1]][A]
                    S=S_prime                
                elif As[A]=='West':
                    S_prime=list(S)
                    S_prime[0]-=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    p_q=random.random()
                    if p_q<0.5:
                        q1_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q2_table[S_prime[0]][S_prime[1]]))-q1_table[S[0]][S[1]][A])
                    else:
                        q2_table[S[0]][S[1]][A]=q2_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q1_table[S_prime[0]][S_prime[1]]))-q2_table[S[0]][S[1]][A])
                    qsum_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+q2_table[S[0]][S[1]][A]
                    S=S_prime
                count+=1
            else:            
                A=np.random.randint(0, len(As))
                if As[A]=='North':        
                    S_prime=list(S)
                    S_prime[1]+=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    p_q=random.random()
                    if p_q<0.5:
                        q1_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q2_table[S_prime[0]][S_prime[1]]))-q1_table[S[0]][S[1]][A])
                    else:
                        q2_table[S[0]][S[1]][A]=q2_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q1_table[S_prime[0]][S_prime[1]]))-q2_table[S[0]][S[1]][A])
                    qsum_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+q2_table[S[0]][S[1]][A]
                    S=S_prime                
                elif As[A]=='South':
                    S_prime=list(S)
                    S_prime[1]-=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    p_q=random.random()
                    if p_q<0.5:
                        q1_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q2_table[S_prime[0]][S_prime[1]]))-q1_table[S[0]][S[1]][A])
                    else:
                        q2_table[S[0]][S[1]][A]=q2_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q1_table[S_prime[0]][S_prime[1]]))-q2_table[S[0]][S[1]][A])
                    qsum_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+q2_table[S[0]][S[1]][A]
                    S=S_prime                
                elif As[A]=='East':
                    S_prime=list(S)
                    S_prime[0]+=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    p_q=random.random()
                    if p_q<0.5:
                        q1_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q2_table[S_prime[0]][S_prime[1]]))-q1_table[S[0]][S[1]][A])
                    else:
                        q2_table[S[0]][S[1]][A]=q2_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q1_table[S_prime[0]][S_prime[1]]))-q2_table[S[0]][S[1]][A])
                    qsum_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+q2_table[S[0]][S[1]][A]
                    S=S_prime                
                elif As[A]=='West':
                    S_prime=list(S)
                    S_prime[0]-=1
                    if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                        S_prime=list(S)
                    p_q=random.random()
                    if p_q<0.5:
                        q1_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q2_table[S_prime[0]][S_prime[1]]))-q1_table[S[0]][S[1]][A])
                    else:
                        q2_table[S[0]][S[1]][A]=q2_table[S[0]][S[1]][A]+alpha*(Rs[S_prime[0]][S_prime[1]]+(gamma*np.max(
                        q1_table[S_prime[0]][S_prime[1]]))-q2_table[S[0]][S[1]][A])
                    qsum_table[S[0]][S[1]][A]=q1_table[S[0]][S[1]][A]+q2_table[S[0]][S[1]][A]
                    S=S_prime
                count+=1
        S=list((0, 0))
        steps_per_episode_double[i][j]=count

Results

For this experiment, we ran the gridworld for 1000 iterations of 50 episodes each with an $\epsilon$ of 0.01, a $\gamma$ of 0.9.

We first show the step-to-goal curve, visualizing the number of steps per episode it took for the agent to reach its goal. We obtain it by counting the number of steps it took for the agent to reach its goal in each episode, then averaging these counts over the 1000 iterations:

In [8]:
average_steps_per_episode_double=np.mean(steps_per_episode_double, axis=0)

plt.plot(average_steps_per_episode_double)
plt.xlabel('Episode')
plt.ylabel('Average number of Steps to reach goal')
plt.show()

Below we can see the V-table for one of the episodes:

In [9]:
v_table_double=np.zeros((5, 5))

for i in range(5):
    for j in range(5):
        v_table_double[i][j]=np.max(qsum_table[i][j])

grid=sns.heatmap(v_table_double, annot=True)
grid
Out[9]:
<matplotlib.axes._subplots.AxesSubplot at 0x202d1f580c8>

Conclusions

We first compare the two step-to-goal curves by placing them on the same plot:

In [10]:
plt.plot(average_steps_per_episode, label='single')
plt.plot(average_steps_per_episode_double, label='double')
plt.xlabel('Episode')
plt.ylabel('Average number of Steps to reach goal')
plt.legend()
plt.show()

From the step to goal curves above, we can conclude that double q-learning converges slower on average than the single q-learning variant. This makes sense as it gathers together two q-values in an ensemble sum and uses them together, but updates both q-values randomly, and should thus find the optimal policy more slowly than the single q-learning variant.

From the V-table, we can see that the optimal policy that the agent learned involves moving East 4 times, and North four times, leading to a rough average of 8 steps per episode. This is a similar policy to the single q-learning variant.

Monte Carlo

Description and Psuedocode

There are two types of Monte Carlo methods: on-policy and off-policy methods. For on-policy methods, we are concerned about learning information about the policy currently being executed. In off-policy methods, we are concerned with learning information of our target policy $\pi$ from our behavior policy b. In this report, we will investigate the applicability of an on-policy Monte-Carlo Control method with an exploring start to our gridworld problem.

A Monte-Carlo exploring start occurs when an agent must explore to find favorable actions. To reduce the amount of time in which this takes place, we must have an eternally soft policy, defined in (4):

$$\pi(a|s)>0$$

for all s and a (4)

An example of such a policy is given in (5):

$$p(a|s)=\epsilon/|A(s)|$$

if not greedy or $1-\epsilon+\epsilon/|A(s)|$ if greedy (5)

It is expected that this policy will converge to the best $\epsilon$-soft policy over time. Psuedocode for an on-policy Monte Carlo control algorithm is given in Figure 3:

In [11]:
img = cv2.imread('Monte Carlo psuedocode.jpg')
plt.figure(figsize=(12, 12))
plt.imshow(img)
plt.xlabel('Figure 3')
plt.show()

Implementation

The rest of our implementation steps are detailed below:

In [12]:
pi=np.empty((5, 5, 4))

runs=1
episodes=50
gamma=0.6
epsilon=0.5

As=np.asarray(['North', 'South', 'East', 'West']) #possible actions

Rs=np.zeros((5, 5)) #initalize rewards for each state
Rs[4][4]=1 #goal state has reward of 1

S=list((0, 0)) #starting state

steps_per_episode_mc=np.empty((runs, episodes))

for i in range(runs):    
    q_table_mc=np.zeros((5, 5, 4))
    for j in range(5):
        for k in range(5):
            for l in range(4):
                pi[j][k][l]=1/len(As)
    returns=[]
    for m in range(episodes):        
        state_list=[]
        action_list=[]
        count=0
        while S !=[4, 4]:
            state_list.append(S)
            action_list.append(A)
            A=np.random.choice(4, 1, replace=True, p=pi[S[0]-1][S[1]-1])            
            if As[A]=='North':        
                S_prime=list(S)
                S_prime[1]+=1
                if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                    S_prime=list(S)               
                S=S_prime                
            elif As[A]=='South':
                S_prime=list(S)
                S_prime[1]-=1
                if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                    S_prime=list(S)                    
                S=S_prime                
            elif As[A]=='East':
                S_prime=list(S)
                S_prime[0]+=1
                if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                    S_prime=list(S)
                S=S_prime                
            elif As[A]=='West':
                S_prime=list(S)
                S_prime[0]-=1
                if S_prime[0] < 0 or S_prime[0] > 4 or S_prime[1] <0 or S_prime[1]>4:
                    S_prime=list(S)            
                S=S_prime
            count+=1            
        S=list((0, 0))        
        G=0
        state_action_list=[]        
        for state in state_list:
            for action in action_list:
                if (state, action) not in state_action_list:
                    state_action_list.append((state, action))                                            
                    if As[action]=='North':
                        if state[1]+1<=4:                        
                            G=gamma*G+Rs[state[0]][state[1]+1]
                        else:
                            G=gamma*G+Rs[state[0]][state[1]]
                    elif As[action]=='South':
                        if state[1]-1>=0:
                            G=gamma*G+Rs[state[0]][state[1]-1]
                        else:
                            G=gamma*G+Rs[state[0]][state[1]]
                    elif As[action]=='East':
                        if state[0]+1<=4:
                            G=gamma*G+Rs[state[0]+1][state[1]]
                        else:
                            G=gamma*G+Rs[state[0]][state[1]]
                    elif As[action]=='West':
                        if state[0]-1>=0:
                            G=gamma*G+Rs[state[0]-1][state[1]]
                        else:
                            G=gamma*G+Rs[state[0]][state[1]]
                    returns.append(G)                    
                    q_table_mc[state[0]][state[1]][action]=np.average(returns)        
        for state in state_list:
            A=np.argmax(q_table_mc[state[0]][state[1]])
            for n in range(len(As)):
                if n==A:                
                    pi[state[0]][state[1]][n]=(1-epsilon)+(epsilon/len(As))                    
                else:
                    pi[state[0]][state[1]][n]=epsilon/len(As)        
        steps_per_episode_mc[i][m]=count

Results

For this experiment, we ran the gridworld for an iteration of 50 episodes with an $\epsilon$ of 0.5, a $\gamma$ of 0.6. These parameter changes were necessary to reduce computational complexity. Due to averaging q-values with the Monte-Carlo method, the agent would often try to move out of the grid, believing that this was the optimal action. Adding in more exploration and reducing the number of iterations helped to solve this.

We first show the step-to-goal curve, visualizing the number of steps per episode it took for the agent to reach its goal. We obtain it by counting the number of steps it took for the agent to reach its goal in each episode, then averaging these counts over the 1000 iterations:

In [13]:
average_steps_per_episode_mc=np.mean(steps_per_episode_mc, axis=0)

print(average_steps_per_episode_mc)

plt.plot(average_steps_per_episode_mc)
plt.xlabel('Episode')
plt.ylabel('Average number of Steps to reach goal')
plt.show()

[  73.  316.   92.   12.   28.   29.  743.  730.   60.  882.   42. 1034.
   92.  623.   46.   37.   18.   78.   50.   28.   33.   57.   30.  139.
  890.   25.  657.   58. 5771.   55.   45.   26.   41.   57.  209.  137.
   17.   47.  155.   54.   17.   11.   20.   55.   41.  348.   44.  272.
  426. 1391.]

Below we can see the V-table for one of the episodes:

In [14]:
v_table_mc=np.zeros((5, 5))

for i in range(5):
    for j in range(5):
        v_table_mc[i][j]=np.max(q_table_mc[i][j])

grid=sns.heatmap(v_table_mc, annot=True)
grid
Out[14]:
<matplotlib.axes._subplots.AxesSubplot at 0x202d2669408>

Conclusions

We first compare the three step-to-goal curves by placing them on the same plot:

In [15]:
plt.plot(average_steps_per_episode, label='single')
plt.plot(average_steps_per_episode_double, label='double')
plt.plot(average_steps_per_episode_mc, label='MC')
plt.xlabel('Episode')
plt.ylabel('Average number of Steps to reach goal')
plt.legend()
plt.show()

Comparing the Monte Carlo results to that of single and double q-learning, we can see that they are inconsistent. This is likely due to the probability distribution of the Monte Carlo method.

However, from the V-table, we can see that the agent has learned the same optimal policy from the previous two experiments. That is, 8 moves that move the agent from (0, 0) to (4, 4) in any order.

Final Remarks and Conclusions

From the experiments in this report, we can conclude that:

  1. The single q-learning variant converged the fastest with the least number of steps out of all 3 methods.

  2. The double q-learning method achieved a comparable, yet slighly worse step-to-goal curve from the single q-learning method.

  3. Our Monte Carlo results were unreliable due to our agent often getting stuck hitting a wall.

References

[1] Ni, Zhen. Monte Carlo supplementary lecture notes-Q leaning examples. p. 15, 2020.

[2] Ni, Zhen. Monte Carlo. Lecture Notes. p. 15, 2020.

[3] Ni, Zhen. Temporal Difference Learning supplementary Lecture Notes- Double Q-learning. p. 4, 2020.